package leetcode.templates.maths;

public class CombMod {
	// 利用费马小定理求C(n, m)
	private int C_Fermat(int n, int m, int p) {
		// C(n, m) = a / b
		long a = multiMod(n, n - m + 1, p); // 分式上面的部分
		long b = multiMod(m, 1, p); // 分式下面的部分
		// 推论2： a/b ≡ a*b^(p-2) (mod p)
		return (int) (a * powMod(b, p - 2, p) % p);
	}

	// = n * (n-1) * (n-2) * ... * m
	private long multiMod(int n, int m, int p) {
		long r = 1;
		for (int i = m; i <= n; i++) {
			r = r * i;
			if (r > p)
				r %= p;
		}
		return r;
	}

	// 快速幂算法
	// a^(2x) = (a^2)^x
	private long powMod(long a, int pow, int p) { // a^pow % p 快速幂算法
		long r = 1;
		while (pow > 0) {
			if ((pow & 1) == 1) { // a^(2x+1) = a*a^(2x)
				r = (r * a) % p;
			}
			a = a * a % p;
			pow >>= 1;
		}
		return r;
	}

}
